// https://leetcode.cn/problems/merge-k-sorted-lists/description/
// 
// 题干：给你一个链表数组，每个链表都已经按升序排列。
// 请你将所有链表合并到一个升序链表中，返回合并后的链表


// 示例：
// 输入：lists = [[1,4,5],[1,3,4],[2,6]]     输出：[1,1,2,3,4,4,5,6]


// 碎语：运用小根堆，熟悉重载()

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
using namespace std;

#include <vector>
#include <queue>

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

struct Cmp
{
    bool operator()(const ListNode* a, const ListNode* b)
    {
        return a->val > b->val;
    }
};

class Solution
{
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;

        for (auto l : lists)
            if (l) heap.push(l);

        auto dummy = new ListNode(-1);
        auto cur = dummy;

        while (!heap.empty())
        {
            auto t = heap.top();
            heap.pop();

            cur->next = t;
            cur = t;

            if (t->next) heap.push(t->next);
        }

        return dummy->next;
    }
};
int main()
{
    ListNode* cur;
    auto l1 = new ListNode(1);
    cur = l1;
    cur->next = new ListNode(4), cur = cur->next;
    cur->next = new ListNode(5), cur = cur->next;

    auto l2 = new ListNode(1);
    cur = l2;
    cur->next = new ListNode(3), cur = cur->next;
    cur->next = new ListNode(4), cur = cur->next;

    auto l3 = new ListNode(2);
    cur = l3;
    cur->next = new ListNode(6), cur = cur->next;

    vector<ListNode*> lists;
    lists.push_back(l1);
    lists.push_back(l2);
    lists.push_back(l3);

    auto head = Solution().mergeKLists(lists);

    while (head)
    {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;

    return 0;
}